{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #3Sum Smaller"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: threeSumSmaller"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #较小的三数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 <code>n</code> 的整数数组和一个目标值 <code>target</code>&nbsp;，寻找能够使条件&nbsp;<code>nums[i] + nums[j] + nums[k] &lt; target</code>&nbsp;成立的三元组&nbsp; <code>i, j, k</code>&nbsp;个数（<code>0 &lt;= i &lt; j &lt; k &lt; n</code>）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong><em>nums</em> = <code>[-2,0,1,3]</code>, <em>target</em> = 2\n",
    "<strong>输出: </strong>2 \n",
    "<strong>解释: </strong>因为一共有两个三元组满足累加和小于 2:\n",
    "&nbsp;    [-2,0,1]\n",
    "     [-2,0,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong><em>nums</em> = <code>[]</code>, <em>target</em> = 0\n",
    "<strong>输出: </strong>0 </pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong><em>nums</em> = <code>[0]</code>, <em>target</em> = 0\n",
    "<strong>输出: </strong>0 </pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>0 &lt;= n &lt;= 3500</code></li>\n",
    "\t<li><code>-100 &lt;= nums[i] &lt;= 100</code></li>\n",
    "\t<li><code>-100 &lt;= target &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [3sum-smaller](https://leetcode.cn/problems/3sum-smaller/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [3sum-smaller](https://leetcode.cn/problems/3sum-smaller/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-2,0,1,3]\\n2', '[]\\n0', '[0]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 3:return 0\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        for i in range(n-2):\n",
    "            if 3*nums[i] >= target:break\n",
    "            for j in range(i+1,n-1):\n",
    "                if nums[i] + 2*nums[j] >= target:break\n",
    "                cnt = bisect.bisect_left(nums[j+1:], target-nums[i]-nums[j]) # 返回小于查找数的数目个数\n",
    "                res += cnt\n",
    "                if cnt <= 0:break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return 0\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-2):\n",
    "            left, right = i+1, len(nums)-1\n",
    "            while left < right:\n",
    "                if nums[i] + nums[left] + nums[right] < target:\n",
    "                    res += (right-left)\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        res, n = 0, len(nums)\n",
    "        for i in range(n-2): # 第一个数位置，0~n-3表示还得留2个数给第2个和第3个（n-2、n-1）\n",
    "            res_sub = 0 # 第一个数是nums[i]的前提下，三数的组合个数\n",
    "            left = i + 1 # 第二个数位置\n",
    "            right = n - 1 # 第三个数位置\n",
    "            while left < right:\n",
    "                if nums[i] + nums[left] + nums[right] < target:\n",
    "                    res_sub += right - left # left确定的条件下，有right-left对儿组合，使之对儿数字和小于target\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1 # 三数和大于等于target，需要right左移，减少三数和\n",
    "            res += res_sub\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(l):\n",
    "            left = target - nums[i]\n",
    "            for j in range(i+1,l):\n",
    "                right = left - nums[j]\n",
    "                for k in range(j+1, l):\n",
    "                    if nums[k] < right:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        break\n",
    "        return ans\n",
    "\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        result = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-2):\n",
    "            left = i + 1\n",
    "            right = n - 1\n",
    "            while left < right:\n",
    "                curr = nums[i] + nums[left] + nums[right]\n",
    "                if curr >= target:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    result += right - left\n",
    "                    left += 1 \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        def double_pointers(left, right=n-1):\n",
    "            count = 0\n",
    "            start = left - 1\n",
    "            while left < right:\n",
    "                if nums[start] + nums[left] + nums[right] < target:\n",
    "                    count += right - left\n",
    "                    left += 1  \n",
    "                else:\n",
    "                    right -= 1\n",
    "\n",
    "\n",
    "            # print(count)\n",
    "            return count\n",
    "        \n",
    "        \n",
    "        # 特殊案例\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            if nums[0] < target:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        \n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        count = 0\n",
    "        while i < n-2:\n",
    "            # print(i)\n",
    "            # if i > 0 and nums[i-1] == nums[i]:  # 由于返回的是下标的三元组，因此无需去重\n",
    "            #     i += 1\n",
    "            #     continue\n",
    "            count += double_pointers(i+1)\n",
    "            i += 1 \n",
    "        \n",
    "        return count \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        # if len(nums) < 3:\n",
    "        #     return 0\n",
    "        # nums.sort()\n",
    "        # l = len(nums)\n",
    "        # ans = 0\n",
    "        # for i in range(l):\n",
    "        #     left = target - nums[i]\n",
    "        #     for j in range(i+1,l):\n",
    "        #         right = left - nums[j]\n",
    "        #         for k in range(j+1, l):\n",
    "        #             if nums[k] < right:\n",
    "        #                 ans += 1\n",
    "        #             else:\n",
    "        #                 break\n",
    "        # return ans\n",
    "        ans = 0\n",
    "        cnt = Counter(nums)\n",
    "        lst = list(cnt.keys())\n",
    "\n",
    "        # x+y+z\n",
    "        for x, y, z in combinations(lst, 3):\n",
    "            if x != y and y != z and x != y and x + y + z < target:\n",
    "                ans += cnt[x] * cnt[y] * cnt[z]\n",
    "\n",
    "        # x+x+x\n",
    "        for x in lst:\n",
    "            if x * 3 < target:\n",
    "                ans += cnt[x] * (cnt[x] - 1) * (cnt[x] - 2) // 6\n",
    "        \n",
    "        for x, y in combinations(lst, 2):\n",
    "            # x+x+y\n",
    "            if x * 2 + y < target:\n",
    "                ans += cnt[y] * cnt[x] * (cnt[x] - 1) // 2\n",
    "            # x+y+y\n",
    "            if x + y * 2 < target:\n",
    "                ans += cnt[x] * cnt[y] * (cnt[y] - 1) // 2\n",
    "        return ans\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        num = 0\n",
    "        start_index= 0\n",
    "        for start_index in range(len(nums)-2):\n",
    "            left_index = start_index +1\n",
    "            right_index= len(nums)-1\n",
    "            while left_index < right_index:\n",
    "                if nums[start_index] + nums[left_index] + nums[right_index] >= target:\n",
    "                    right_index -=1\n",
    "                else:\n",
    "                    num += (right_index-left_index)\n",
    "                    left_index += 1\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums)<3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(nums)-2):\n",
    "            left = i + 1\n",
    "            right = len(nums) -1 \n",
    "            while left < right:\n",
    "                if nums[left] + nums[right] < target - nums[i]:\n",
    "                    ans += right - left\n",
    "                    left +=1\n",
    "                else:\n",
    "                    right -=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for a in range(len(nums)-2):\n",
    "            b, c = a + 1, len(nums) - 1\n",
    "            while b < c:\n",
    "                if nums[b] + nums[c] < target - nums[a]:\n",
    "                    res += c - b \n",
    "                    b += 1\n",
    "                elif nums[b] + nums[c] >= target - nums[a]:\n",
    "                    c -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n-2):\n",
    "            x = nums[i]\n",
    "            right = n-1\n",
    "            for j in range(i+1,n-1):\n",
    "                y = nums[j]\n",
    "                if x+y+nums[j+1]>=target:\n",
    "                    break\n",
    "                left= j+1\n",
    "                while left<=right:\n",
    "                    mid = (right-left)//2+left\n",
    "                    if nums[mid]+x+y<target:\n",
    "                        left = mid+1\n",
    "                    else:\n",
    "                        right = mid-1\n",
    "                res+=right-j\n",
    "                right = min(n-1,right+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort() \n",
    "        n = len(nums) \n",
    "\n",
    "        ans = 0 \n",
    "\n",
    "        def lower_bound(nums, k, l, r):\n",
    "            while (l < r):\n",
    "                mid = (l + r) >> 1 \n",
    "                if nums[mid] >= k:\n",
    "                    r = mid \n",
    "                else:\n",
    "                    l = mid + 1 \n",
    "            return l \n",
    "\n",
    "\n",
    "        for i in range(n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                k = target - nums[i] - nums[j] \n",
    "                idx = lower_bound(nums, k, j+1, n-1) \n",
    "                if nums[idx] < k:\n",
    "                    ans += idx - j \n",
    "                else:\n",
    "                    ans += idx - j - 1 \n",
    "        \n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            l, r = i + 1, n - 1\n",
    "            while l < r:\n",
    "                three = nums[i] + nums[l] + nums[r]\n",
    "                if three >= target:\n",
    "                    r -= 1\n",
    "                else: # [-1, -1, -1, 0, 1, 1, 1], 2\n",
    "                    res += r - l\n",
    "                    l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        r=n-1\n",
    "        ans=0\n",
    "        print(nums)\n",
    "        for i in range(n):\n",
    "            l=i+1\n",
    "            r=n-1\n",
    "            while l<r:\n",
    "                if nums[i]+nums[l]+nums[r]>=target:\n",
    "                    r=r-1\n",
    "                else:\n",
    "                    ans+=r-l\n",
    "                    l=l+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        if not nums  or len(nums)<3:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        if sum(nums[-3:])<target:\n",
    "            return len(nums)-2\n",
    "        if sum(nums[:3])>=target:\n",
    "            return 0\n",
    "        res = 0\n",
    "        for i in range(len(nums)-2):\n",
    "            l = i+1\n",
    "            r = len(nums) -1 \n",
    "            while l < r:\n",
    "                if nums[i] + nums[l] + nums[r] < target:\n",
    "                    res = res + r - l\n",
    "                    l+=1\n",
    "                else:\n",
    "                    r -= 1\n",
    "        return res \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        if not nums and len(nums) < 3:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "        for i in range(len(nums)-2):\n",
    "            for j in range(i+1, len(nums)-1):\n",
    "                if nums[j+1] >= target-nums[i]-nums[j]:\n",
    "                    continue\n",
    "                if nums[-1] < target-nums[i]-nums[j]:\n",
    "                    count = count + len(nums)-1 - j\n",
    "                    continue\n",
    "                k = self.binary_search(nums, j, target-nums[i]-nums[j])\n",
    "                count = count + k-j\n",
    "        return count\n",
    "\n",
    "    def binary_search(self, nums, start, target):\n",
    "        low = start\n",
    "        high =  len(nums)  - 1\n",
    "        while low < high:\n",
    "            mid = (high-low + 1) // 2 + low\n",
    "            if nums[mid] < target:\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return low \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n-2):\n",
    "            j, k = i + 1, n - 1\n",
    "            while j < k:\n",
    "                cur = nums[i] + nums[j] + nums[k]\n",
    "                if cur >= target:\n",
    "                    k -= 1\n",
    "                else:\n",
    "                    ans += k - j\n",
    "                    j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(l):\n",
    "            left = target - nums[i]\n",
    "            for j in range(i+1,l):\n",
    "                right = left - nums[j]\n",
    "                for k in range(j+1, l):\n",
    "                    if nums[k] < right:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        break\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        for i in range(n-2):\n",
    "            res += self.twoSumSmaller(nums, i+1, target-nums[i])\n",
    "        return res\n",
    "\n",
    "    def twoSumSmaller(self, nums, start, target):\n",
    "        num_small = 0\n",
    "        n = len(nums)\n",
    "        left,right = start,n-1\n",
    "        while left < right:\n",
    "            sum_ = nums[left] + nums[right]\n",
    "            if sum_ < target:\n",
    "                num_small += right-left\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "        return num_small"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        length = len(nums)\n",
    "        sorted_nums = sorted(nums)\n",
    "        res = 0\n",
    "\n",
    "        for start in range(length-2):\n",
    "            remained_target = target - sorted_nums[start]\n",
    "\n",
    "            i = start + 1\n",
    "            j = length - 1\n",
    "\n",
    "            while i < j:\n",
    "                if sorted_nums[j] + sorted_nums[i] >= remained_target:\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    res += (j - i)\n",
    "                    i += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums) \n",
    "        nums.sort() \n",
    "        ans = 0 \n",
    "        for i in range(2, n):\n",
    "            j = i-1\n",
    "            k = 0 \n",
    "            while k < j:\n",
    "                while k < j and nums[j] + nums[k] >= target - nums[i]:\n",
    "                    j-=1 \n",
    "                ans += j - k \n",
    "                k += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] >= 1 / 3 * target:\n",
    "                continue\n",
    "            l, r = i + 1, n - 1\n",
    "            while l < r:\n",
    "                three = nums[i] + nums[l] + nums[r]\n",
    "                if three >= target:\n",
    "                    r -= 1\n",
    "                elif three < target:\n",
    "                    res += r - l\n",
    "                    l += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        if not nums or n < 3:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i <= n - 3:\n",
    "            j = i + 1\n",
    "            k = n - 1\n",
    "            while j < k:\n",
    "                if nums[i] + nums[j] + nums[k] < target:\n",
    "                    ans += (k - j)\n",
    "                    j = j + 1\n",
    "                    k = n - 1\n",
    "                else:\n",
    "                    k = k - 1\n",
    "            i += 1\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            l,r = i+1,n-1\n",
    "            need = target - nums[i]\n",
    "            while l < r:\n",
    "                sumNum = nums[r] + nums[l]\n",
    "                if sumNum >= need:\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    ans +=  r - l\n",
    "                    l += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        size = len(nums)\n",
    "        res = 0\n",
    "        for i in range(size):\n",
    "            left, right = i + 1, size - 1\n",
    "            while left < right:\n",
    "                total = nums[i] + nums[left] + nums[right]\n",
    "                if total < target:\n",
    "                    res += (right - left)\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        if not nums and len(nums) < 3:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "        for i in range(len(nums)-2):\n",
    "            for j in range(i+1, len(nums)-1):\n",
    "                if nums[j+1] >= target-nums[i]-nums[j]:\n",
    "                    continue\n",
    "                k = self.binary_search(nums, j, target-nums[i]-nums[j])\n",
    "                count = count + k-j\n",
    "        return count\n",
    "\n",
    "    def binary_search(self, nums, start, target):\n",
    "        low = start\n",
    "        high =  len(nums)  - 1\n",
    "        while low < high:\n",
    "            mid = (high-low + 1) // 2 + low\n",
    "            if nums[mid] < target:\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return low \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        #使nums[i] + nums[j] + nums[k] < target\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            left,right=i+1,n-1\n",
    "            while left < right:\n",
    "                res = nums[i] + nums[left] +nums[right]\n",
    "                if res < target:\n",
    "                    ans+=right-left\n",
    "                    left+=1\n",
    "                else:\n",
    "                    right-=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        \n",
    "        count = 0\n",
    "        for i in range(n - 2):\n",
    "            left, right = i + 1, n - 1\n",
    "            while left < right:\n",
    "                temp_sum = nums[i] + nums[left] + nums[right]\n",
    "                if temp_sum < target:\n",
    "                    count += (right - left)\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        if not nums  or len(nums)<3:\n",
    "            return 0\n",
    "\n",
    "        nums.sort()\n",
    "        if sum(nums[-3:])<target:\n",
    "            return len(nums)-2\n",
    "        if sum(nums[:3])>=target:\n",
    "            return 0\n",
    "        res = 0\n",
    "        for i in range(len(nums)-2):\n",
    "            l = i+1\n",
    "            r = len(nums) -1 \n",
    "            while l < r:\n",
    "                if nums[i] + nums[l] + nums[r] < target:\n",
    "                    res = res + r - l\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "        return res \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        def double_pointers(left, right):\n",
    "            count = 0\n",
    "            start = left - 1\n",
    "            while left < right:\n",
    "                cur_sum = nums[start] + nums[left] + nums[right]\n",
    "                if cur_sum < target:\n",
    "                    count += right - left\n",
    "                    left += 1  \n",
    "                else:\n",
    "                    right -= 1\n",
    "\n",
    "\n",
    "            # print(count)\n",
    "            return count\n",
    "        \n",
    "        n = len(nums)\n",
    "        # 特殊案例\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            if nums[0] < target:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        \n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        count = 0\n",
    "        while i < n-2:\n",
    "            # print(i)\n",
    "            # if i > 0 and nums[i-1] == nums[i]:  # 由于返回的是下标的三元组，因此无需去重\n",
    "            #     i += 1\n",
    "            #     continue\n",
    "            count += double_pointers(i+1, n-1)\n",
    "            i += 1 \n",
    "        \n",
    "        return count \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return 0\n",
    "\n",
    "        count = 0\n",
    "        nums.sort()\n",
    "        \n",
    "        for i in range(len(nums) - 2):\n",
    "            left, right = i + 1, len(nums) - 1\n",
    "            while left < right:\n",
    "                if nums[i] + nums[left] + nums[right] < target:\n",
    "                    count += right - left\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) < 3:  # 处理边界条件\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(nums) - 2):  # 注意i,j,k三个指针不能重合\n",
    "            left = i + 1\n",
    "            right = len(nums) - 1\n",
    "            while left < right:\n",
    "                # 如果left和right之和小于target-nums[i]，left右移\n",
    "                if nums[left] + nums[right] < target - nums[i]:\n",
    "                    ans += right - left #### 统计的是原组的个数\n",
    "                    left += 1 \n",
    "                # 如果left和right之和大于target-nums[i]，right左移\n",
    "                else:\n",
    "                    right -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums=sorted(nums)\n",
    "        ret=0\n",
    "        def get_num(i,target):\n",
    "            temp=0\n",
    "            left=i+1\n",
    "            right=len(nums)-1\n",
    "            while left<right:\n",
    "                if nums[left]+nums[right]<target:\n",
    "                    temp+=right-left\n",
    "                    left+=1\n",
    "                else:\n",
    "                    right-=1\n",
    "            return temp\n",
    "        for i in range(len(nums)-2):\n",
    "            ret+=get_num(i,target-nums[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0;\n",
    "        for i in range(n-2):\n",
    "            x = nums[i]\n",
    "            left,right=i+1,n-1\n",
    "            while left<right:\n",
    "                if x+nums[left]+nums[right]<target:\n",
    "                    res+=right-left\n",
    "                    left+=1\n",
    "                else:\n",
    "                    right-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        return sum(bisect.bisect_left(nums, target - nums[j] - nums[k], 0, j)\n",
    "            for k in range(len(nums)) for j in range(k)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_right\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        psa = [float('-inf')] * (len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            psa[i + 1] = max(psa[i] , nums[i]) #always increasing after sorted\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1 , len(nums)):\n",
    "                k = bisect_left(psa , target - nums[i] - nums[j]) - 2\n",
    "                if k - j > 0:\n",
    "                    res += k - j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        ans = 0\n",
    "        cnt = Counter(nums)\n",
    "        lst = list(cnt.keys())\n",
    "\n",
    "        # x+y+z\n",
    "        for x, y, z in combinations(lst, 3):\n",
    "            if x != y and y != z and x != y and x + y + z < target:\n",
    "                ans += cnt[x] * cnt[y] * cnt[z]\n",
    "\n",
    "        # x+x+x\n",
    "        for x in lst:\n",
    "            if x * 3 < target:\n",
    "                ans += cnt[x] * (cnt[x] - 1) * (cnt[x] - 2) // 6\n",
    "        \n",
    "        for x, y in combinations(lst, 2):\n",
    "            # x+x+y\n",
    "            if x * 2 + y < target:\n",
    "                ans += cnt[y] * cnt[x] * (cnt[x] - 1) // 2\n",
    "            # x+y+y\n",
    "            if x + y * 2 < target:\n",
    "                ans += cnt[x] * cnt[y] * (cnt[y] - 1) // 2\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n - 1, 1, -1):\n",
    "            new_tar = target - nums[i]\n",
    "            l, r = 0, i - 1\n",
    "            while r > 0:\n",
    "                l = min(l, r)\n",
    "                while l < r and nums[l] + nums[r] < new_tar:\n",
    "                    l += 1\n",
    "                ans += l \n",
    "                r -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        n,res=len(nums),0\n",
    "        nums.sort()\n",
    "        for i,j in itertools.combinations(range(n),2):\n",
    "            res+=max(0,bisect_left(nums,target-nums[i]-nums[j])-j-1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        cnt1 = Counter()\n",
    "        cnt2 = Counter()\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            for j in cnt2:\n",
    "                if i + j < target:\n",
    "                    res += cnt2[j]\n",
    "            for j in cnt1:\n",
    "                cnt2[i + j] += cnt1[j]\n",
    "            cnt1[i] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def func(self, nums: List[int], L: int, target: int) -> int:    #两个数的和小于target\n",
    "    #     res = 0\n",
    "    #     R = len(nums) - 1\n",
    "    #     while L < R:\n",
    "    #         if nums[L] + nums[R] < target:\n",
    "    #             res += (R - L)\n",
    "    #             L += 1\n",
    "    #         else:\n",
    "    #             R -= 1\n",
    "    #     return res\n",
    "\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "    #     n = len(nums)\n",
    "    #     nums.sort()\n",
    "    #     res = 0\n",
    "    #     for i in range(n - 2):      #3个数的和，分解成2个数的和  先固定住一个变量，控制变量\n",
    "    #         res += self.func(nums, i + 1, target - nums[i])\n",
    "    #     return res\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        res = 0\n",
    "        for i in range(len(nums)-2):\n",
    "            left = i+1\n",
    "            right = len(nums)-1\n",
    "            res_sm = target-nums[i]\n",
    "            while left < right:\n",
    "                if nums[right]+nums[left] < res_sm:\n",
    "                    res += (right-left)\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import *\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        len_n = len(nums)\n",
    "        cnt = 0\n",
    "        for i in range(len_n):\n",
    "            for j in range(i+1, len_n):\n",
    "                vi, vj = nums[i], nums[j]\n",
    "                vk = target - vi - vj\n",
    "                idx = bisect_left(nums, vk)\n",
    "                if idx-1 > j:\n",
    "                    cnt += idx-1 -j\n",
    "        \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        answer = 0\n",
    "        n      = len(nums)\n",
    "        for i in range(n - 2):\n",
    "            j = i + 1\n",
    "            k = n - 1\n",
    "\n",
    "            while j < k:\n",
    "                threeSum = nums[i] + nums[j] + nums[k]\n",
    "                if threeSum < target:\n",
    "                    answer += k - j\n",
    "                    j += 1\n",
    "                else:\n",
    "                    k -= 1\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def func(self, nums: List[int], L: int, target: int) -> int:    #两个数的和小于target\n",
    "        res = 0\n",
    "        R = len(nums) - 1\n",
    "        while L < R:\n",
    "            if nums[L] + nums[R] < target:\n",
    "                res += (R - L)\n",
    "                L += 1\n",
    "            else:\n",
    "                R -= 1\n",
    "        return res\n",
    "\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i in range(n - 2):      #3个数的和，分解成2个数的和  先固定住一个变量，控制变量\n",
    "            res += self.func(nums, i + 1, target - nums[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if target-nums[i]-nums[j] > nums[j]:\n",
    "                    cur = bisect_left(nums,target-nums[i]-nums[j])-1\n",
    "                    # print(i,j,cur,ans)\n",
    "                    ans += cur - j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        res, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] >= 1 / 3 * target:\n",
    "                continue\n",
    "            l, r = i + 1, n - 1\n",
    "            while l < r:\n",
    "                three = nums[i] + nums[l] + nums[r]\n",
    "                if three >= target:\n",
    "                    r -= 1\n",
    "                else: # [-1, -1, -1, 0, 1, 1, 1], 2\n",
    "                    res += r - l\n",
    "                    l += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        ret=0\n",
    "        nums=sorted(nums)\n",
    "        i=0\n",
    "        while i<len(nums):\n",
    "            j=i+1\n",
    "            judge_=0\n",
    "            while j<len(nums):\n",
    "                k=j+1\n",
    "                judge=0\n",
    "                while k<len(nums):\n",
    "                    if nums[i]+nums[j]+nums[k]<target:\n",
    "                        ret+=1\n",
    "                        judge=1\n",
    "                        judge_=1\n",
    "                    else:\n",
    "                        break\n",
    "                    k+=1\n",
    "                if judge==0:\n",
    "                    break\n",
    "                j+=1\n",
    "            i+=1\n",
    "            if judge_==0:\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeSumSmaller(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        def twoSumSmaller(seq, target):\n",
    "            res = 0\n",
    "            left = 0\n",
    "            right = len(seq)-1\n",
    "            while left != right:\n",
    "                if seq[left] + seq[right] < target:\n",
    "                    res += right - left\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "            return res\n",
    "        res = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            seq = nums[i+1:]\n",
    "            res += twoSumSmaller(seq, target - nums[i])\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
